package C045;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: C03
 * Package: C045
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/7 20:07
 * @Version 1.0
 * @Since 1.0
 */
public class C03 {
    public static void main(String[] args) {

    }

    public static List<String> findWords(char[][] board, String[] words) {
        // 构建前缀树
        build(words);
        ArrayList<String> ans = new ArrayList<>();
        // 遍历每一个格子, 获取元素
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, i, j, 0, ans);
            }
        }
        clear();
        return ans;
    }
    public static void clear() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(arr[i], 0);
            pass[i] = 0;
            end[i] = null;
        }
    }
    // i 行位置
    // j 为列位置
    // t 为当前的前缀树的层数
    // 返回包含了几个前缀树的节点
    private static int dfs(char[][] board, int i, int j, int t, ArrayList<String> ans) {
        if(i <0 || i == board.length || j < 0 || j == board[0].length || board[i][j] == 0) {
            return 0;
        }

        int index = board[i][j] - 'a';
        // 前缀树底下没有字符串
        if(arr[t][index] == 0) {
            return 0;
        }
        int cur = arr[t][index];
        if(pass[cur] == 0) {
            return 0;
        }

        int res = 0;
        if(end[cur] != null) {
            res ++;
            ans.add(end[cur]);
            end[cur] = null;
        }

        // 上下左右
        char tmp = board[i][j];
        board[i][j] = 0;
        res += dfs(board, i - 1, j, cur, ans);
        res += dfs(board, i + 1, j, cur, ans);
        res += dfs(board, i, j - 1, cur, ans);
        res += dfs(board, i, j + 1, cur, ans);

        pass[t] -= res;
        board[i][j] = tmp;
        return res;
    }

    static int MAXLEN = 30001;
    static int[][] arr = new int[MAXLEN][26];
    static int cnt = 0;

    static int[] pass = new int[MAXLEN];
    static String[] end = new String[MAXLEN];

    // 构建前缀树
    private static void build(String[] words) {
        for (int i = 0; i < words.length; i++) {
            insert(words[i]);
        }
    }

    // 插入元素
    private static void insert(String word) {
        char[] charArray = word.toCharArray();
        int index, cur = 0;
        pass[cur] ++;
        for (int i = 0; i < charArray.length; i++) {
            index = charArray[i] - 'a';
            if(arr[cur][index] == 0) {
                arr[cur][index] = ++cnt;
            }
            cur = arr[cur][index];
            pass[cur] ++;
        }
        end[cur] = word;
    }

}
